package code.oldCode.dynamic;

import utils.TreeNode;

import java.util.*;

public class DynamicTree {

    /**
     * 96. 不同的二叉搜索树
     *
     * @param n
     * @return
     */
    public int numTrees(int n) {
        // 1:1 2:2 3:5
        int[] dp = new int[n + 1];
        dp[0] = 0; // 其实这里 dp[0] = 1 比较合理，代表一种情况，空树也代表一种情况，这样下面就不用分情况了
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int root = 1; root <= i; root++) {
                if (root == 1) {
                    dp[i] += dp[i - root];
                } else if (root == i) {
                    dp[i] += dp[root - 1];
                } else {
                    dp[i] += dp[root - 1] * dp[i - root];
                }
            }
        }
        return dp[n];
    }

    /**
     * 95. 不同的二叉搜索树 II
     *
     * @param n
     * @return
     */
    public List<TreeNode> generateTrees(int n) {
        return getTreeList(1, n);
    }

    /**
     * 并非DP，而是递归，但是好理解
     */
    public List<TreeNode> getTreeList(int start, int end) {
        List<TreeNode> list = new ArrayList<>();
        if (start > end) {
            list.add(null);
            return list;
        }
        if (start == end) {
            list.add(new TreeNode(start));
            return list;
        }
        for (int root = start; root <= end; root++) {
            List<TreeNode> leftList = getTreeList(start, root - 1);
            List<TreeNode> rightList = getTreeList(root + 1, end);
            for (TreeNode leftTree : leftList) {
                for (TreeNode rightTree : rightList) {
                    TreeNode rootNode = new TreeNode(root);
                    rootNode.left = leftTree;
                    rootNode.right = rightTree;
                    list.add(rootNode);
                }
            }
        }

        return list;
    }

    /**
     * dp思路：从上一次的 n 个结果中添加最新的数（也是当前最大的），可以是在根节点，也可以是在根节点的右孩子的某个位置
     */
    public List<TreeNode> generateTrees_dp(int n) {
        if (n == 0) return new ArrayList<>();
        List<TreeNode>[] dp_lists = new List[n + 1];
        dp_lists[0] = new ArrayList<>();
        dp_lists[0].add(null);
        // 一共增加n个数字
        for (int i = 1; i <= n; i++) {
            dp_lists[i] = new ArrayList<>();
            // 遍历之前的所有解
            for (TreeNode treeNode : dp_lists[i - 1]) {
                // 插入到根节点，之前的解作为左孩子
                TreeNode newTreeNode = new TreeNode(i);
                newTreeNode.left = treeNode;
                dp_lists[i].add(newTreeNode);
                // 插入到右孩子，考虑最极端的情况，最多有 i - 1 种情况，j表示向右多少
                for (int j = 0; j < i - 1; j++) {
                    TreeNode copyTree = treeCopy(treeNode);
                    TreeNode right = copyTree;
                    // 如果 right == null 说明这个treeNode没有那么深，break，后面的情况更不可能。
                    int k = 0;
                    while (k < j && right != null) {
                        right = right.right;
                        k++;
                    }
                    if (right == null) break;
                    // 从这里开始，插入，原来右面的挂在插入节点的左面
                    TreeNode rightTree = right.right;
                    newTreeNode = new TreeNode(i);
                    right.right = newTreeNode;
                    newTreeNode.left = rightTree;
                    dp_lists[i].add(copyTree);
                }
            }
        }

        return dp_lists[n];
    }

    /**
     * 复制一个树
     */
    public TreeNode treeCopy(TreeNode originTree) {
        if (originTree == null) return null;
        TreeNode newTree = new TreeNode(originTree.val);
        newTree.left = treeCopy(originTree.left);
        newTree.right = treeCopy(originTree.right);
        return newTree;
    }

    /**
     * 337. 打家劫舍 III
     *
     * @param root
     * @return
     */
    public int rob(TreeNode root) {
        // 打家劫舍的树版，自己的方法，用层次遍历的反向
        if (root == null) return 0;
        // 对应每个节点的dp树
        HashMap<TreeNode, Integer> hashDP = new HashMap<>();
        hashDP.put(null, 0);
        // 从底层向上遍历，层次遍历的逆向
        Queue<TreeNode> queue = new ArrayDeque<>();
        List<TreeNode> list = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode front = queue.poll();
            list.add(front);
            if (front.left != null) queue.offer(front.left);
            if (front.right != null) queue.offer(front.right);
        }
        Collections.reverse(list);
        TreeNode[] array = list.toArray(new TreeNode[0]);
        // 反向层次遍历，更新dp树
        for (TreeNode treeNode : array) {
            // 不选这个节点，选他的左右子树的最大值之和
            int dp_left = hashDP.get(treeNode.left);
            int dp_right = hashDP.get(treeNode.right);
            int dont_select_treeNode = dp_left + dp_right;
            // 选这个节点，选左子树的左右子树和右子树的左右子树之和
            int dp_left_left = (treeNode.left != null && treeNode.left.left != null) ? hashDP.get(treeNode.left.left) : 0;
            int dp_left_right = (treeNode.left != null && treeNode.left.right != null) ? hashDP.get(treeNode.left.right) : 0;
            int dp_right_left = (treeNode.right != null && treeNode.right.left != null) ? hashDP.get(treeNode.right.left) : 0;
            int dp_right_right = (treeNode.right != null && treeNode.right.right != null) ? hashDP.get(treeNode.right.right) : 0;
            int select_treeNode = treeNode.val + dp_left_left + dp_left_right + dp_right_left + dp_right_right;

            int max = Math.max(select_treeNode, dont_select_treeNode);
            hashDP.put(treeNode, max);
        }

        return hashDP.get(array[array.length - 1]);
    }

    /**
     * 官解，用DFS遍历，比较巧妙，不用层次遍历那么麻烦
     */
    public int rob_dfs(TreeNode root) {
        HashMap<TreeNode, Integer> selectThis = new HashMap<>();
        HashMap<TreeNode, Integer> dontSelectThis = new HashMap<>();
        dfs(root, selectThis, dontSelectThis);
        return Math.max(selectThis.getOrDefault(root, 0), dontSelectThis.getOrDefault(root, 0));
    }

    public void dfs(TreeNode root, HashMap<TreeNode, Integer> y, HashMap<TreeNode, Integer> n) {
        if (root == null) return;
        dfs(root.left, y, n);
        dfs(root.right, y, n);
        y.put(root, root.val + n.getOrDefault(root.left, 0) + n.getOrDefault(root.right, 0));
        n.put(root, Math.max(y.getOrDefault(root.left, 0), n.getOrDefault(root.left, 0)) + Math.max(y.getOrDefault(root.right, 0), n.getOrDefault(root.right, 0)));
    }

    public static void main(String[] args) {
        DynamicTree dynamicTree = new DynamicTree();
        System.out.println(dynamicTree.numTrees(3));
    }
}
